Trong lĩnh vực lý thuyết đồ thị, một cây là biểu tượng hình học cho sự trật tự. Khác với các mạng lưới hỗn loạn nơi có thể tồn tại nhiều con đường dẫn đến cùng một đích, một cây cung cấp một hành trình duy nhất và độc nhất giữa hai điểm bất kỳ. Rào cản cấu trúc này không phải là hạn chế mà chính là nền tảng của các hệ thống phân cấp — từ dòng họ tổ tiên của các vị thần Hy Lạp đến cấu trúc thư mục trong hệ điều hành hiện đại.
1. Cấu tạo của một cây
Trước khi hệ thống phân cấp xuất hiện, ta có cây tự do. Định nghĩa của nó rất đơn giản nhưng tinh tế:
Định nghĩa 9.1.1
Một (cây tự do) $T$ là một đồ thị đơn mà với mọi cặp đỉnh $v$ và $w$, tồn tại một đường đi đơn độc duy nhất từ $v$ đến $w$. Điều này ngụ ý rằng đồ thị vừa là liên thông và không chu trình (không có chu trình).
Khi ta chỉ định một đỉnh cụ thể làm "nguồn gốc", ta sẽ tạo ra một cây có gốc. Sự biến đổi này tạo ra một hướng không gian, nơi các mối quan hệ được xác định bởi khoảng cách và hướng từ gốc.
Từ vựng phân cấp
Trong một cây có gốc $v_0$, hãy xem xét một đường đi đơn giản $(v_0, v_1, \dots, v_n)$:
- Cha: Đỉnh $v_{n-1}$ là cha của $v_n$.
- Con: $v_n$ là con của $v_{n-1}$.
- Anh em ruột: Các đỉnh có cùng cha.
- Tiền nhân: Tất cả các đỉnh trên đường đi từ gốc đến $v_n$ (trừ chính $v_n$ trong một số ngữ cảnh).
- Hậu duệ: Tất cả các đỉnh có $v$ là tiền nhân.
Các chỉ số cấu trúc
- Mức độ: Độ dài của đường đi duy nhất từ gốc đến một đỉnh. Gốc nằm ở mức độ 0.
- Chiều cao: Số mức độ lớn nhất có trong cây.
- Lá (đỉnh cuối): Một đỉnh không có con — điểm kết thúc của một nhánh.
- Đỉnh nội bộ (nhánh): Một đỉnh có ít nhất một con.
🎯 Khái niệm cốt lõi: Cây con
Một cây con là một tập con của cây gồm một đỉnh và tất cả các hậu duệ của nó. Trong hệ thống tập tin, đây là một thư mục và mọi tập tin/thư mục con bên trong nó. Trong Hình 9.2.1, dòng dõi của Kronos (Zeus, Poseidon, Hades, Ares) là một cây con của Uranus.
2. Ứng dụng thực tế
Cây không chỉ là những khái niệm trừu tượng trong toán học. Chúng là xương sống của sự tổ chức:
- Hệ thống tập tin máy tính: 'C:' là gốc; thư mục là các đỉnh nội bộ; tập tin là các lá.
- Biểu đồ quản lý: CEO là gốc; các giám đốc là các nút nội bộ; các thành viên cá nhân là các lá.
- Khung quyết định: Giải các bài toán như Instant Insanity hoặc phân tích tính phẳng của n-cube thường liên quan đến việc duyệt qua các không gian trạng thái dạng cây.